package 另一棵树的子树;
import 相同的树.TreeNode;

class Solution {
    //判断subRoot是不是root的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //两棵树相同返回真
        if (isSameTree(root,subRoot)){
            return true;
        }
        //上面if语句已经包含判断root与subRoot都为null的情况了
        //所以这里当root为null时subRoot一定不为null,停止递归,返回假
        if(root == null){
            return false;
        }
        //递归判断root的左子树与右子树,看看有没有与subRoot相同的树,有就返回真
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    //判断p与q两棵树相吧相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两棵树都是空树那么他们相同
        if (p == null && q == null){
            return true;
        }else if (p == null || q == null){
            //当一棵树为空一棵树不为空,他们不相同
            return false;
        }
        //判断当前根结点值是否相同
        if(p.val == q.val){
            //根结点值相同,递归判断他们左子树,右子树是否相同,
            //只有都相同才代表两棵树相同
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
        //执行到这说明两棵树不相同返回false
        return false;
    }
}